#include <stdio.h>
#include <limits.h>

#define TAB_SYMBOL '\t'
#define SPACE_SYMBOL ' '
#define NEWLINE_SYMBOL '\n'
#define ENDLINE_SYMBOL '\0'

int GetString(char str[], unsigned short int strMaxLength);
void LowerHexNumber(char digits[], unsigned short int numberLength);
void SqueezeSymbols(char s1[], char s2[]);
short int FirstMatchPosition(char s1[], char s2[]); 
int Power(int base, int n);
unsigned int GetBits(unsigned int x, int p, int n);
unsigned int SetBits(unsigned int x, unsigned int p, unsigned int n, unsigned int y);
unsigned int InvertBits(unsigned int x, unsigned int p, unsigned int n);
unsigned short int RightRot(unsigned short int x, unsigned short int n);
unsigned short int BitCount(unsigned long int x);
void LowerString(char str[]);
int BinSearch(unsigned short int x, unsigned short int v[], unsigned short int n);
void PrintEscapes(char str[], unsigned short int length);
void HideEscapes(char str[], unsigned short int length);




// GetString: Reads one line from the input and stores it in the array, returns line length.
int GetString(char str[], unsigned short int strMaxLength)
{
    char c;
    unsigned short int i;

    for (i=0; (i<strMaxLength-1) && ((c=getchar()) != EOF && c != NEWLINE_SYMBOL); ++i) {
        str[i] = c;
    }
    str[i] = ENDLINE_SYMBOL;

    return i;
}



// LowerHexNumber: Lowers the 'A' - 'Z' and 'X' hex symbols.
void LowerHexNumber(char digits[], unsigned short int numberLength)
{
    unsigned short int i;

    for (i=0; i<numberLength; i++) {
        if (digits[i] >= 'A' && digits[i] <= 'F') {
            digits[i] = digits[i] + 'a' - 'A';
        } else if (digits[i] == 'X') {
            digits[i] = 'x';
        }
    }
}


// SqueezeSymbols: Gets two strings. Removes from the first string all symbols that are present in s2.
void SqueezeSymbols(char s1[], char s2[]) {
    unsigned short int i;
    unsigned short int j;
    unsigned short int k;
    unsigned short int ifFound;

    for (i=k=0; s1[i] != ENDLINE_SYMBOL; i++) {
        ifFound = 0;
        for(j=0; s2[j] != ENDLINE_SYMBOL; j++) {
            if (s1[i] == s2[j]) {
                ifFound = 1;
            }
        }
        if (ifFound == 0) {
            s1[k++] = s1[i];
        }
    }
    s1[k] = ENDLINE_SYMBOL;
}


// FirstMatchPosition ("any"): Gets two strings, returns the number of the position of first character found in s1 hat is also present in s2. If no match - returns -1.
short int FirstMatchPosition(char s1[], char s2[]) {
    short int i;
    short int j;

    for (i=0; s1[i] != ENDLINE_SYMBOL; i++) {
        for (j=0; s2[j] != ENDLINE_SYMBOL; j++)
            if (s1[i] == s2[j])
                return i;
    }
    return -1;
}

// Power: returns the "base" in "n"-th power (n>=0)
int Power(int base, int n) {
    int p;

    p = 1;
    for (p=1; n>0; --n) {
        p = base*p;
    }
    return p;
}


// GetBits: extracts n bins of x, starting from position p
unsigned int GetBits(unsigned int x, int p, int n) {
    return (x >> (p+1-n)) & ~(~0 << n);
}


//SetBits: Ex. 2.6
unsigned int SetBits(unsigned int x, unsigned int p, unsigned int n, unsigned int y) {
    x = x & ~((Power(2,n)-1) << p);
    y = y & (Power(2,n)-1);
    y = y << p;
    return x | y;
}

// InvertBits: Ex. 2.7
unsigned int InvertBits(unsigned int x, unsigned int p, unsigned int n) {
    unsigned int x_copy;

    x_copy = x;
    x = x & ~(~(~0 << n) << p);
    x_copy = ~x_copy & (~(~0 << n) << p);
    return x | x_copy;
}


// RightRot: Ex. 2.8
unsigned short int RightRot(unsigned short int x, unsigned short int n) {
    unsigned short int i;
    unsigned short int mask;

    for (i=0; i<n; ++i) {
        if (1 & x) { // ends with "1"
            x = x >> 1;
            x = x | ~(USHRT_MAX >> 1);
        } else {
            x = x >> 1;
        }
    }

    return x;
}


// BitCount: Ex. 2.9
unsigned short int BitCount(unsigned long int x) {
    unsigned short int b;

    for (b = 0; x != 0; x &= (x-1)) {
            b++;
    }
    return b;
}


// LowerString: Replaces all the capital letters in the string with non-capital. English ASCII only.
void LowerString(char str[]) {
    unsigned short int i;

    for (i=0; str[i] != '\0'; i++) {
        str[i] = ((str[i] >= 'A') && (str[i] <= 'Z')) ? str[i]+32 : str[i];
    }
}


// BinSearch: Returns the position of x in v[0] < v[1] < v[2] < ... < v[n-1]
int BinSearch(unsigned short int x, unsigned short int v[], unsigned short int n) {
    unsigned short int low;
    unsigned short int high;
    unsigned short int mid;

    low = 0;
    high = n-1;
    while (low <= high) {
        mid = (low + high) / 2;
        if (x < v[mid])
            high = mid - 1;
        else if (x > v[mid])
            low = mid + 1;
        else
            return mid;
    }

    return -1;
}


// PrintEscapes: Reads the string, converts containing \t and \n to the corresponding letters for displaying.
void PrintEscapes(char str[], unsigned short int length) {
    unsigned short int c;

    for (c = 0; c < length; c++) {
        switch (str[c]) {
            case TAB_SYMBOL:
                printf("\\t");
                break;
            case NEWLINE_SYMBOL:
                printf("\\n");
                break;
            default:
                putchar(str[c]);
                break;
        }
    }
}


// HideEscapes: Reads the string, converts containing letters sequence "\t" and "\n" to the escape sequences \t and \n.
void HideEscapes(char str[], unsigned short int length) {
    unsigned short int c;
    unsigned short int ifEscape;

    ifEscape = 0;

    for (c = 0; c < length; c++) {
        switch (str[c]) {
            case '\\':
                ifEscape = 1;
                break;
            default:
                if (ifEscape) {
                    switch (str[c]) {
                        case 't':
                            putchar('\t');
                            ifEscape = 0;
                            break;
                        case 'n':
                            putchar('\n');
                            ifEscape = 0;
                            break;
                        default:
                            putchar('\\');
                            putchar(str[c]);
                            ifEscape = 0;
                            break;
                    }
                } else {
                    putchar(str[c]);
                }
                break;
        }
    }
}
